package study.datastructure.grip;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2025-02-17 16:00
 * <p>
 * 2025/2/17,
 * <p>
 * 2025/2/17,
 * <p>
 * 2025/2/17,
 * <p>
 * 2025/2/17,
 */

/**
 2025/2/17,
 */

import study.datastructure.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 图论
 */
public class s1 {

    /**
     * 岛屿的周长
     * @param grid
     * @return
     */
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int l = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return dfs1(grid, i, j);

                }

            }
        }
        return 0;
    }

    private int dfs2(int[][] grid, int row, int col) {
        if (!inArea(grid, row, col)) {
            return 1;
        }

        if (grid[row][col] == 0) {
            return 1;
        }

        if (grid[row][col] != 1) {
            return 0;
        }

        grid[row][col] = 2;

        return dfs2(grid, row - 1, col) + dfs2(grid, row + 1, col) + dfs2(grid, row, col - 1) + dfs2(grid, row, col + 1);

    }

    /**
     * 岛屿的最大面积
     * @param grid
     * @return
     */
    public int maxAreaOfIsland(int[][] grid) {

        if (grid == null || grid.length == 0) return 0;

        int l = grid.length;
        int n = grid[0].length;
        int resArea = 0;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int curr = dfs1(grid, i, j);
                    resArea = Math.max(curr, resArea);
                }

            }
        }
        return resArea;
    }

    private int dfs1(int[][] grid, int row, int col) {
        if (!inArea(grid, row, col)) {
            return 0;
        }

        if (grid[row][col] != 1) {
            return 0;
        }

        grid[row][col] = 2;

        return 1 + dfs1(grid, row - 1, col) + dfs1(grid, row + 1, col) + dfs1(grid, row, col - 1) + dfs1(grid, row, col + 1);

    }

    /**
     * 岛屿数量
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int l = grid.length;
        int n = grid[0].length;

        int resNums = 0;

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    resNums++;
                    dfs(grid, i, j);
                }

            }

        }
        return resNums;
    }

    private void dfs(char[][] grid, int row, int col) {
        if (!inArea(grid, row, col)) {
            return;
        }

        if (grid[row][col] != '1') {
            return;
        }
        grid[row][col] = '2';

        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);

    }

    private boolean inArea(char[][] grid, int row, int col) {
        return 0 <= row && row < grid.length && 0 <= col && col < grid[0].length;
    }

    /**
     * 图论 基本框架
     * @param grid
     * @param r
     * @param c
     */
    void dfs(int[][] grid, int r, int c) {
        // 判断 base case
        if (!inArea(grid, r, c)) {
            return;
        }
        // 如果这个格子不是岛屿，直接返回
        if (grid[r][c] != 1) {
            return;
        }
        grid[r][c] = 2; // 将格子标记为「已遍历过」

        // 访问上、下、左、右四个相邻结点
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    // 判断坐标 (r, c) 是否在网格中
    boolean inArea(int[][] grid, int r, int c) {
        return 0 <= r && r < grid.length
                && 0 <= c && c < grid[0].length;
    }

    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0;
        int minutes = 0;

        // 初始化队列和新鲜橘子数量
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        // 如果没有新鲜橘子，直接返回0
        if (fresh == 0) {
            return 0;
        }

        // 四个方向
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // BFS遍历
        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();
            minutes++;
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                // 四个方向的坐标 如果有新鲜的橘子就腐烂
                for (int[] dir : directions) {
                    int x = current[0] + dir[0];
                    int y = current[1] + dir[1];
                    if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) {
                        grid[x][y] = 2; // 腐烂新鲜橘子
                        queue.offer(new int[]{x, y});
                        fresh--;
                    }
                }
            }
        }

        // 如果还有新鲜橘子，返回-1
        return fresh == 0 ? minutes : -1;
    }

    /**
     * bfs框架
     * @param root
     */
    void bfs(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

}
